package com.cd.algorithm.leetcode;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * 无重复字符的最长子串
 * 解题思路为滑动窗口
 *
 * 例如字符串  abba
 *   定义开始、结束双指针，或着叫左、右
 *   第一镒循环取的 指针为  0，0  字符串 a
 *   第二次循环取的 指针为  0，1  字符串 ab
 *   第三次循环取  发现第二个b和第一个b一样，则开始指针变为第一个b的坐标+1，目前最大字符串为ab
 *   第四次循环取  发现第二个a，此时字符串为ba ，循环结束，最大字符串长度为2
 *
 * 在每一步的操作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，
 * 但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；
 *   在枚举结束后，我们找到的最长的子串的长度即为答案
 *
 */
public class Topic3 {
    @Test
    public void test() {
        String s = "abba";
        System.out.println(lengthOfLongestSubstring(s));
    }

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.equals("")) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        int max = 0;
        for (int start = 0, end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            if(map.containsKey(c)){
                //在这比较是为了防止abba这种，
                // 在遍历到第二个b的时候，start应该为第一个b的下标加1，遍历到第二个a的时候，map.get(c)==0，
                //此时的start应该为应该取   上面这两个的最大，不能取map.get(c)+1
                //也就是start的值必须越来越大，不能比现在的小
                start = Math.max(map.get(c)+1,start);
            }
            max = Math.max(max,end-start+1);
            map.put(c,end);
        }
        return max;
    }
}
